| 翻訳と辞書 |
path cover
Given a directed graph ''G'' = (''V'', ''E''), a path cover is a set of directed paths such that every vertex ''v'' ∈ ''V'' belongs to at least one path. Note that a path cover may include paths of length 0 (a single vertex).〔, Section 2.5.〕
A ''path cover'' may also refer to a vertex-disjoint path cover, i.e., a set of paths such that every vertex ''v'' ∈ ''V'' belongs to ''exactly'' one path.〔.〕
==Properties==
A theorem by Gallai and Milgram shows that the number of paths in a smallest path cover cannot be larger than the number of vertices in the largest independent set.〔, Theorem 2.5.1.〕 In particular, for any graph ''G'', there is a path cover ''P'' and an independent set ''I'' such that ''I'' contains exactly one vertex from each path in ''P''. Dilworth's theorem follows as a corollary of this result.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「path cover」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|